|
|
Event Report 15th Prolog Programming Contest
Bart Demoen
K.U.Leuven Belgium
|
|
Editor: Enrico Pontelli
|
After
organizing the Prolog Programming Contest 14 times, you would think
that we have seen it all. Not so: the 15th PPC had some new surprises.
But let's start from the beginning ...
Many
years ago, it was quite a drag to find teams and at the ICLP welcome
reception, we awere always trying to lure people into participating,
for instance by trying to make them feel guilty for refusing to
participate and also by refuting their petty excuses. At the end of
the reception, we usually had enough teams (and drinks). In recent
years, there is no more need for that: people show up willingly without
having to pressurize them. Again so this year: we had ten teams. All
teams had three members, except the team of Paul Tarau: it has one
member only: this tradition started at the JICSLP in Manchester
1996. After the initial hassle just before the contest
starts - people want their laptop connected to power and
extension cords are always scarce - the questions are distributed: one
set of questions for each team, except for Paul, who can get two
copies. Similar for the laptops: it is stricktly one per team, but Paul
can use two. And then the teams start programming, or rather, they
first tear up the sheets with the problems, so that they can read them
independently, and then decide which problem to tackle first. This is
important, as speed can make the difference at the end. Moreover,
as soon as a team submits a solution, its members get chocolate. Until
very recently, nobody realized that this first solution need not be
correct ...
Already after 10 seconds, a team pointed out that the "pixels" problem had an error in the example - it couldn't start better.
At
some point, a team asked whether it was allowed to use setarg/3 for the
"pixels" problem: of course that is allowed, but why would you ?
Eventually, three teams used setarg/3 and all three were punished by
having to resubmit several times.
Close
to the end, several teams asked whether they could hand in the solution
on paper .. now, that is new ! The prescribed method is on a memory
stick, but since the keyboard is a bottleneck in this sort of
competitions, teams have often more solutions on paper than typed in.
So
things went pretty normal, until one team decided to withdraw
during the competition: the contest rules do not provide such a withdrawing
option, so we refused the withdrawal and disqualified the team. We had
to disqualify two other teams for using assert and retract: that is
explicitly forbidden - but who reads the rules ? We can't remember ever
having disqualified any team before and suddenly this year, there were
three!
The
other teams did quite good, but also made consistently the same errors.
For instance, the "chain" problem could be solved by making
partitions of a given number, where all members are mutually prime, but
the teams invariably choose to generate all permutations of N elements,
and then do a costly operation for each of them. That means that
strictly speaking, no-one solved that problem, because even for small
N, the timeout was reached, or a LOCAL STACK overflow. We were more
lenient than that.
Another problem was apparently that in the
"pixels" problem, the two sentences: each square contains a number
larger than (or equal to) 1 and the input always contains an
even number of pixels with a particular number larger than 1
seemed to
suggest that there would be no ones in the input. It is great to
make fun of programmers under pressure, isn't it ? But really, we have
great admiration for anyone willing to risk his/her reputation in such a contest, and so should you.
Now
for the results: on average the teams did well. Each team solved two
problems. During the ICLP banquet, the wrong team of Italians was
announced as the runner up. So now for good: the second best team had
Agostino Dovier, Andrea Formisano and Enrico Pontelli as members. They
solved three problems. Agostino ended 3th last year, so it
looks promising for next year. The winning team consisted of Marco
Gavanelli,
Tom Schrijvers and Peter Stuckey: they solved four problems. Since
Peter has been winning this contest so many times now, it is worth
analysing his technique and strategy, especially since he hardly knows
any Prolog (as one of his team members told me). We have
been unable to
understand completely how he does it, but here are two essential
ingredients: Peter hardly reads the problem statement and he starts
programming before he has a clue about its solution. It is the true
spirit of extreme programming, which seems to come naturally to him.
One day, hopefully, Peter will write up his strategy in more detail!
Let
us finish by thanking people: Maria Garcia de la Banda and Enrico
Pontelli for letting us organise the contest in their conference; Agostino
Dovier for provding a good room, a good time slot, and even the only
session that started in time; the sponsors of this contest: the ALP and
in particular Gopal Gupta through his company Interoperate (http://www.interoperate.biz/). And finally the participants with the guts to subject themselves to potential humiliation.
We hope to see you in the future and we promise to have better chocolates next time !
|